package org.libermundi.theorcs.core.model.impl;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.libermundi.theorcs.core.exceptions.NodeNotFoundException;
import org.libermundi.theorcs.core.model.Node;
import org.libermundi.theorcs.core.model.NodeData;
import org.libermundi.theorcs.core.model.Tree;

/**
 * Represents a Tree of Objects of generic type T. The Tree is represented as
 * a single rootElement which points to a List<Node<T>> of children. There is
 * no restriction on the number of children that a particular node may have.
 * This Tree provides a method to serialize the Tree into a List by doing a
 * pre-order traversal. It has several methods to allow easy updation of Nodes
 * in the Tree.
 */
public class TreeImpl<T extends NodeData> implements Tree<T> {
 
    private Node<T> rootElement;
    
    private Map<String, Node<T>> _flatNodeCache;
     
    /**
     * Default Constructor
     */
    public TreeImpl() {
        _flatNodeCache = new HashMap<>();
    }
    
    public TreeImpl(Node<T> rootElement) {
        this();
        setRootElement(rootElement);
    }    
 
    /*
     * (non-Javadoc)
     * @see org.libermundi.theorcs.core.model.Tree#getRootElement()
     */
    @Override
	public Node<T> getRootElement() {
        return this.rootElement;
    }
 
    /*
     * (non-Javadoc)
     * @see org.libermundi.theorcs.core.model.Tree#setRootElement(org.libermundi.theorcs.core.model.Node)
     */
    @Override
	public void setRootElement(Node<T> rootElement) {
        this.rootElement = rootElement;
    }
     
    /*
     * (non-Javadoc)
     * @see org.libermundi.theorcs.core.model.Tree#toList()
     */
    @Override
	public List<Node<T>> toList() {
        List<Node<T>> list = new ArrayList<>();
        walk(rootElement, list);
        return list;
    }
    
    /*
     * (non-Javadoc)
     * @see org.libermundi.theorcs.core.model.Tree#getElement(java.lang.String)
     */
	@Override
	public Node<T> getElement(String id) throws NodeNotFoundException {
		Node<T> result = _flatNodeCache.get(id); 
		if(result == null) {
			result = getRootElement().getChild(id);
			if(result == null) {
				throw new NodeNotFoundException();
			}
			//Put the Element in Cache
			_flatNodeCache.put(id,result);
		}
		return result;
	}    
     
    /**
     * Returns a String representation of the Tree. The elements are generated
     * from a pre-order traversal of the Tree.
     * @return the String representation of the Tree.
     */
    @Override
	public String toString() {
        return toList().toString();
    }
     
    /**
     * Walks the Tree in pre-order style. This is a recursive method, and is
     * called from the toList() method with the root element as the first
     * argument. It appends to the second argument, which is passed by reference     * as it recurses down the tree.
     * @param element the starting element.
     * @param list the output of the walk.
     */
    private void walk(Node<T> element, List<Node<T>> list) {
        list.add(element);
        for (Node<T> data : element.getChildren()) {
            walk(data, list);
        }
    }

}